/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-12-14
 * Time: 下午 07:29
 */
public class MyBTree {
    public static final int M = 3;
    static class BTNode {
        public int[] keys; //关键字
        public BTNode[] subs; //孩子
        public BTNode parent; //孩子节点的父节点
        public int usedSize; //当前节点中关键字的数量
        public BTNode() {
            //方便分裂，我们多加一个
            this.keys = new int[M];
            this.subs = new BTNode[M + 1];
        }
    }
    public BTNode root;//当前树的根节点

    /**
     * 插入数据
     * @param key 需要插入的数据
     * @return 是否插入
     */
    public boolean insert (int key) {
        // 1.如果节点为空，则直接设定为根节点
        if (root == null) {
            root = new BTNode();
            root.keys[0] = key;
            root.usedSize++;
            return true;
        }
        // 2.查找是否存在该节点,并且存在
        Pair<BTNode, Integer> pair = find(key);
        if (pair.getVal() != -1) return false;
        //3.如果节点不存在，开始插入
        BTNode parent = pair.getKey();
        int i = parent.usedSize - 1;
        for ( ;i >= 0; i--) {
            if (parent.keys[i] >= key) {
                parent.keys[i + 1] = parent.keys[i];
            }else break;
        }
        parent.keys[i + 1] = key;
        parent.usedSize++;
        if (parent.usedSize >= M) split(parent);
        return true;
    }

    /**
     * 查找key值
     * @param key
     * @return 找到了就返回找到节点以及其下标，没找到就返回父节点以及-1
     */
    public Pair<BTNode, Integer> find (int key) {
        BTNode cur = root;
        BTNode parent = null;
        while (cur != null) {
            int i = 0;
            for ( ;i < cur.usedSize; i++) {
                if (cur.keys[i] == key)  return new Pair<>(cur, i); //找到的节点和其下标
                else if (cur.keys[i] > key) break;
            }
//            while (i < cur.usedSize) {
//                if (cur.keys[i] == key)  return new Pair<>(cur, i); //找到的节点和其下标
//                else if (cur.keys[i] < key) i++;
//                else break;
//            } 博哥代码
            parent = cur;
            cur = cur.subs[i];
        }
        return new Pair<>(parent, -1);
    }
    /**
     * 分裂的逻辑
     * @param node 需要分裂的节点
     */
    public void split (BTNode node) {
        BTNode newNode = new BTNode();
        //1.先存储当前需要分裂的节点的父节点
        BTNode parent = node.parent;
        //2.开始挪数据
        int mid = node.usedSize >> 1;
        int i = mid + 1;
        int j = 0;
        for (; i < node.usedSize; i++) {
            newNode.keys[j] = node.keys[i];
            newNode.subs[j] = node.subs[i];

            //处理刚刚拷贝过来的孩子节点的父亲节点
            if (newNode.subs[j] != null) {
                newNode.subs[j].parent = newNode;
                node.subs[i] = null;
            }
            node.usedSize--;
            newNode.usedSize++;
            j++;
        }
        //多拷贝一次孩子节点
        newNode.subs[j] = node.subs[i];
        node.subs[i] = null;
        if (newNode.subs[j] != null) {
            newNode.subs[j].parent = newNode;
        }
        //特殊：处理根节点的情况
        if (node == root) {
            root = new BTNode();
            root.keys[0] = node.keys[mid];
            root.subs[0] = node;
            root.subs[1] = newNode;
            root.usedSize = 1;
            node.usedSize--;
            node.parent = root;
            newNode.parent = root;
            return;
        }

        //更新当前节点的父节点
        newNode.parent = parent;
        //开始移动父亲节点
        int endP = parent.usedSize - 1; //**********
        int midVal = node.keys[mid];
        for (;endP >= 0; endP--) {
            if (parent.keys[endP] >= midVal) {
                parent.keys[endP + 1] = parent.keys[endP];
                parent.subs[endP + 2] = parent.subs[endP + 1];
            }else break;
        }
        parent.keys[endP + 1] = midVal;
        node.usedSize--;
        //将当前父节点的孩子节点更改为newNode
        parent.subs[endP + 2] = newNode;
        parent.usedSize++;
        if (parent.usedSize >= M) split(parent);
    }
    public void inorder(){
        inorderChild(root);
    }
    public void inorderChild(BTNode root){
        if(root == null)
            return;
        for(int i = 0; i < root.usedSize; ++i){
            inorderChild(root.subs[i]);
            System.out.print(root.keys[i] + " ");
        } inorderChild(root.subs[root.usedSize]);
    }
}
